package com.zjj.algorithm.learning.atguigu.tree.search;

import com.zjj.algorithm.learning.atguigu.tree.TreeNode;

/**
 * 二叉排序树
 * @author zjj_admin
 * @date 2022/12/3 10:01
 */
public class BinarySearchTreeDemo {

    public static void main(String[] args) {
        /**
         *                     7
         *           3                10
         *       1       5        9         12
         *
         *
         *            4    6            11        22
         *                                    20
         *
         */
        int[] arr = new int[]{7, 3, 10, 12, 5, 1, 9};
        SortTree sortTree = new SortTree();

        for (int i = 0; i < arr.length; i++) {
            sortTree.addNode(new SortNode(arr[i]));
        }

        sortTree.midOrder();
        System.out.println();
        System.out.println("删除2");
        sortTree.del(2);
        sortTree.midOrder();


        System.out.println();
        System.out.println("删除7");
        sortTree.del(7);
        sortTree.midOrder();


        System.out.println();
        System.out.println("删除9");
        sortTree.del(9);
        sortTree.midOrder();


        System.out.println();
        System.out.println("删除12");
        sortTree.del(12);
        sortTree.midOrder();

    }


}

/**
 * 二叉排序树
 */
class SortTree {

    /**
     * 二叉排序树的根节点
     */
    private SortNode root;

    public void addNode(SortNode node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

    public SortNode searchNode(int val) {
        if (this.root == null) {
            return null;
        } else {
            return this.root.searchNode(val);
        }
    }


    public SortNode searchParentNode(int val) {
        if (this.root == null) {
            return null;
        } else {
            if (this.root.no == val) {
                return null;
            }
            return this.root.searchParentNode(val);
        }
    }


    /**
     * 删除二叉排序树的节点
     * 1、删除叶子结点
     * 通过目标节点（target）的父节点，通过父节点直接删除
     * 2、删除只有一颗子树的节点
     * 将父节点指向目标节点的指针指向目标节点的子节点即可
     * 3、删除有两颗子树的节点
     * 3.1：可以选择从左子树中寻找最大的节点替换目标节点
     * 3.2：可以选择从右子树中寻找最小的节点替换目标节点
     *
     * @param val 目标节点
     */
    public void del(int val) {
        if (this.root == null) {
            return;
        }
        //获取目标节点
        SortNode targetNode = searchNode(val);
        //当没有找到目标节点时，直接返回
        if (targetNode == null) {
            return;
        }
        //获取父节点
        SortNode parentNode = searchParentNode(val);
        if (parentNode == null) {
            //根节点没有子节点时，说明根节点就是目标节点，删除根节点即可
            if (root.left == null && root.right == null) {
                this.root = null;
            }
            if (root.right != null && root.left == null) {
                root = root.right;

            }
            if (root.left != null && root.right == null) {
                root = root.left;
            }
            if (root.left != null && root.right != null) {
                SortNode minNode = this.root.right.getMinNode();
                SortNode temp = new SortNode(minNode.no);
                //将原始的最小的节点删除
                del(minNode.no);
                //让临时节点成为根节点
                this.root = temp;
                temp.left = targetNode.left;
                temp.right = targetNode.right;
                //最后将右侧的最小的节点删除

            }
        } else {
            //当目标节点是叶子节点是
            if (targetNode.left == null && targetNode.right == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = null;
                } else {
                    parentNode.right = null;
                }
                return;
            }
            //当目标节点只存在一个子节点时
            //当父节点的左节点是目标节点，并且目标节点的右子节点为 null 时
            if (targetNode.right == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = targetNode.left;
                } else {
                    parentNode.right = targetNode.left;
                }
                return;
            }
            if (targetNode.left == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = targetNode.right;
                } else {
                    parentNode.right = targetNode.right;
                }
                return;
            }

            //当目标节点存在两个子节点时
            //获取右子树中的最小的节点
            SortNode rightMinNode = targetNode.right.getMinNode();
            SortNode temp = new SortNode(rightMinNode.no);
            del(rightMinNode.no);
            if (parentNode.left == targetNode) {
                parentNode.left = temp;
                temp.left = targetNode.left;
                temp.right = targetNode.right;
            }
            if (parentNode.right == targetNode) {
                parentNode.right = temp;
                temp.left = targetNode.left;
                temp.right = targetNode.right;
            }

        }


    }


    public void midOrder() {
        if (this.root == null) {
            System.out.println("二叉排序树没有节点，不能中序遍历");
        } else {
            this.root.midOrder();
        }
    }

}


/**
 * 二叉排序树的节点
 */
class SortNode {
    int no;
    SortNode left;
    SortNode right;

    public SortNode(int no) {
        this.no = no;
    }

    /**
     * 添加节点，需要满足二叉排序树的要求
     *
     * @param node
     */
    public void add(SortNode node) {
        if (node == null) {
            return;
        }
        //当当前节点大于 node 时，就将 node 添加到当前节点的左子节点上
        if (this.no > node.no) {
            if (this.left == null) {
                this.left = node;
            } else {
                //当左子节点不为null时，就递归遍历添加到左子节点
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                //当右子节点不为null时，就递归遍历添加到右子节点
                this.right.add(node);
            }
        }
    }

    /**
     * 查找节点
     *
     * @param val
     * @return
     */
    public SortNode searchNode(int val) {
        if (this.no == val) {
            return this;
        } else if (val > this.no) {
            if (this.right == null) {
                return null;
            }
            return this.right.searchNode(val);
        } else {
            if (this.left == null) {
                return null;
            }
            return this.left.searchNode(val);
        }
    }


    /**
     * 寻找节点的父节点
     *
     * @param val
     * @return
     */
    public SortNode searchParentNode(int val) {
        if (this.left != null && this.left.no == val) {
            return this;
        }
        if (this.right != null && this.right.no == val) {
            return this;
        }
        if (this.left != null && val < this.no) {
            return this.left.searchParentNode(val);
        } else if (this.right != null && val >= this.no) {
            return this.right.searchParentNode(val);
        }
        return null;
    }

    /**
     * 获取最小的节点
     *
     * @return
     */
    public SortNode getMinNode() {
        if (this.left == null) {
            return this;
        } else {
            return this.left.getMinNode();
        }
    }


    /**
     * 中序遍历
     */
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.print(this + "  ");
        if (this.right != null) {
            this.right.midOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }


}